package com.Earth01;
/*
* 面试题 08.01. 三步问题
* */
public class Earth240720 {
    public static void main(String[] args) {
        int n = 3;
        int res = waysToStep(n);
        System.out.println(res);
    }
    public static int waysToStep(int n) {
        /*斐波那契数列*/
        if(n <= 2) return n;
        long a = 1;
        long b = 1;
        long c = 2;
        long t = 0;
        for(int i = 3; i <= n; i++){
            t = (c + b + a)%1000000007;
            a = b;
            b = c;
            c = t;
        }
        return (int)t;
    }
}
